#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back
#define vec vector<int>

int read(){int x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);return x*sgn;}

const int N = 1.5e5+10;
const int L = N * 3;

int n,m,ct[L],bas,a[N];

struct stree{
	int mn,cnt,ans,lz;
}t[L<<2];

void tag(int x,int c){t[x].mn += c; t[x].ans = t[x].mn == 0 ? t[x].cnt : 0; t[x].lz += c;}

void pushdown(int x){if(t[x].lz){tag(x << 1,t[x].lz); tag(x << 1 | 1,t[x].lz); t[x].lz = 0;}}

void pushup(int x){
	t[x].mn = min(t[x << 1].mn,t[x << 1 | 1].mn);
	t[x].cnt = (t[x << 1].mn == t[x].mn ? t[x << 1].cnt : 0) + (t[x << 1 | 1].mn == t[x].mn ? t[x << 1 | 1].cnt : 0);
	t[x].ans = t[x].mn == 0 ? t[x].cnt : 0;
}

void build(int o = 1,int l = 1,int r = L){
	if(l == r) return t[o].cnt = t[o].ans = 1,void(); int mid = l + r >> 1;
	build(o << 1,l,mid); build(o << 1 | 1,mid + 1,r); pushup(o);
}

void upd(int xl,int xr,int v,int o = 1,int l = 1,int r = L){
	if(xl == l && xr == r) return tag(o,v); pushdown(o); int mid = l + r >> 1;
	if(xr <= mid) upd(xl,xr,v,o<<1,l,mid); else if(xl > mid) upd(xl,xr,v,o<<1|1,mid+1,r);
	else upd(xl,mid,v,o<<1,l,mid),upd(mid+1,xr,v,o<<1|1,mid+1,r); pushup(o);
}

int query(int xl,int xr,int o = 1,int l = 1,int r = L){
	if(xl == l && xr == r) return t[o].ans; pushdown(o); int mid = l + r >> 1;
	if(xr <= mid) return query(xl,xr,o<<1,l,mid); else if(xl > mid) return query(xl,xr,o<<1|1,mid+1,r);
	else return query(xl,mid,o<<1,l,mid) + query(mid+1,xr,o<<1|1,mid+1,r);
}

void modify(int x,int tp){
	int ps = x - ct[x] + (tp == -1);
	upd(ps,ps,tp); ct[x] += tp;
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in; bas = N; build();
	for(int i = 1;i <= n;i++) a[i] = in + bas,modify(a[i],1);
	while(m--){
		int p = in,x = in;
		if(p){
			if(a[p] <= n + bas) modify(a[p],-1);
			else --ct[a[p]];
			a[p] = x + bas;
			if(a[p] <= n + bas) modify(a[p],1);
			else ++ct[a[p]];
		}else if(x > 0){
			int ps = n + bas; --bas;
			if(ct[ps]) upd(ps - ct[ps] + 1,ps,-1);
		}else{
			++bas; int ps = n + bas;
			if(ct[ps]) upd(ps - ct[ps] + 1,ps,1);
		}
		printf("%d\n",query(bas + 1,bas + n));
	}
	return 0;
}
